<?php

/**
* nestedTree class for basic items/subitems
* manipulations
*
* Copyright (c) 2003-2009 Krasimir Kazakov, kk@drun.net
*
* This is a FREE, LGPL-ed code, see
* http://www.fsf.org/copyleft/lgpl.html for more.
*
* @author Krasimir Kazakov <kk@drun.net>
* @author Vasil Martinov <vasil.martinov@gmail.com>
* @version 1.4
* @package nestedTree
* @link http://knowledge.drun.net/viewtopic.php?id=37
*/
class nestedTree extends model{
	var $db_handle = null;
	var $db_table = '';
	var $primary = '';
	var $left = '';
	var $right = '';
	var $level = '';

	public function __construct($modelName=NULL){
		parent::__construct($modelName);
	}

	// initializes the tree
	public function nestedTree($db,$table, $table_primary = 'tree_id',
		$table_left = 'tree_left', $table_right = 'tree_right',
		$table_level = 'tree_level') {

		$this->db_handle = $db;
		$this->db_table = $table;
		$this->primary = $table_primary;
		$this->left = $table_left;
		$this->right = $table_right;
		$this->level = $table_level;
	}

	public function getAllParents($id, $return_root = true){
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$result = array();

		if ($return_root) {
			$sql = "SELECT * FROM $f_table ORDER BY $f_left DESC";
		} else {
			$sql = "SELECT * FROM $f_table WHERE $f_level != 0
				ORDER BY $f_left DESC";
		}

		$sth = $this->db_handle->Query($sql);

		while ($row = $sth->fetchRow()) {

			if (($row[$f_primary] == $id) && (count($result) == 0)) {
				$result[] = $row;
			} elseif (count($result) != 0) {
				$cnt_prev = count($result) - 1;

				if (($row[$f_left] < $result[$cnt_prev][$f_left]) &&
				($row[$f_right] > $result[$cnt_prev][$f_right]) &&
				($row[$f_level] == ($result[$cnt_prev][$f_level] - 1)))

				$result[] = $row;
			}
		}
		return $result;
	}

	public function parentId($id) {
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$sql = "SELECT * FROM $f_table WHERE $f_primary = $id";

		$cat_details = $this->db_handle->getRow($sql);
		$cat_left = $cat_details[$f_left];
		$cat_right = $cat_details[$f_right];
		$cat_level = $cat_details[$f_level];

		$sql = "SELECT * FROM $f_table
			WHERE $f_left < $cat_left AND
				$f_right > $cat_right AND
				$f_level = ".($cat_level - 1);
		$cat_parent = $this->db_handle->getRow($sql);
		if (is_array($cat_parent)) {
			if (isset($cat_parent[$f_primary])) {
				return $cat_parent[$f_primary];
			}
		}
		return 0;
	}

	public function sort($sort_id, $direction){
		if ($direction == '') {
			return false;
		}

		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$iParentId = $this->parentId($sort_id);
		$tmp = $this->nstGetNodeWhere($iParentId);
		$iParentLeft = (int) $tmp['l']; $iParentRight = (int) $tmp['r'];

		$iParentLevel = (int) $tmp['lvl'];

		// get all entries that are on the same level and from the
		// same parent
		$aSortableEntries = array_values($this->db_handle->getAssoc("SELECT $f_primary, $f_primary
			FROM $f_table WHERE ($f_left > $iParentLeft) AND
			($f_right < $iParentRight) AND ($f_level = ($iParentLevel + 1))
			ORDER BY $f_left ASC"));


		$iSwapId = 0;

		foreach ($aSortableEntries as $iEachId => $iEachEntry) {
			if ($iEachEntry == $sort_id) {
				if ($direction == 'down') {
					if (isset($aSortableEntries[$iEachId+1])) {
						$iSwapId = $aSortableEntries[$iEachId+1];
					}
				} elseif ($direction == 'up') {
					if (isset($aSortableEntries[$iEachId-1])) {
						$iSwapId = $aSortableEntries[$iEachId-1];
					}
				}
			}
		}

		if ($iSwapId > 0) {
			if ($direction == 'down') {
				$this->nstMoveToNextSibling($sort_id, $iSwapId);
			} else {
				$this->nstMoveToPrevSibling($sort_id, $iSwapId);
			}
		} else {
			return false;
		}
		return true;
	}





	function details($id) {
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$sql = "SELECT * FROM $f_table WHERE $f_primary = $id";

		$cat_details = $this->db_handle->getRow($sql);
		return $cat_details;
	}

	// clears the tree completely
	function clearTree() {
		// this is for easy reading of the SQL
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$this->db_handle->Query("TRUNCATE $f_table");
		$this->db_handle->Query("INSERT INTO $f_table
			($f_left, $f_right, $f_level) VALUES(1, 2, 0)");
		return true;
	}

	function insertRecord($parent_id, $table_values = array()) {
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		if ($parent_id == 0) {
			$parent_id = 1; // fix for cid = 0's
		}

		if (!is_array($table_values)) {
			return false;
		}

		$parent_values = $this->db_handle->getRow("SELECT * FROM $f_table
			WHERE $f_primary = $parent_id");

		if (!is_array($parent_values)) {
			return false;
		}
		$parent_left = (int) $parent_values[$this->left];
		$parent_right = (int) $parent_values[$this->right];
		$parent_level = (int) $parent_values[$this->level];

		// create space for the new record
		$sql = "UPDATE IGNORE $f_table SET
			$f_left  = IF ( $f_left > $parent_right, $f_left + 2, $f_left),
			$f_right = IF ( $f_right >= $parent_right, $f_right + 2, $f_right)
			WHERE $f_right >= $parent_right";
		$this->db_handle->Query($sql);

		$node_left = $parent_right;
		$node_right = $node_left + 1;
		$node_level = $parent_level + 1;

		$sql = "INSERT INTO $f_table SET
			$f_left = $node_left, $f_right = $node_right,
			$f_level = $node_level";

		// add the extra fields
		$have_sort_key = '';
		foreach ($table_values as $key => $val) {

			if (substr($key, -4) == 'sort') {
				$have_sort_key = addslashes($key);

			} else {
				$val = addslashes($val);
				$sql .= ", $key = '$val' ";
			}
		}
		$this->db_handle->Query($sql);

		$new_id = (int) mysql_insert_id();

		// initialize sort column to be as the newly inserted id to
		// handle correctly sorting after this
		if ($have_sort_key != '') {
			$this->db_handle->Query("UPDATE $f_table SET `$have_sort_key` = $new_id
				WHERE `$f_primary` = $new_id");
		}

		return $new_id;
	}

	function deleteRecord($record_id, $delete_children = false) {
		// this is for easy reading of the SQL
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		if ($record_id == 0) {
			return false;
		}
		$node_values = $this->db_handle->getRow("SELECT * FROM $f_table
			WHERE $f_primary = $record_id");

		if (!is_array($node_values)) {
			return false;
		}
		$node_left = (int) $node_values[$this->left];
		$node_right = (int) $node_values[$this->right];
		$node_level = (int) $node_values[$this->level];

		if ($delete_children) {
			// if to delete all the children
			$node_temp = ($node_right - $node_left) + 1;

			// delete records
			$sql = "DELETE FROM $f_table
				WHERE ($f_left BETWEEN $node_left AND $node_right)";
			$this->db_handle->Query($sql);

			// clear blanks
			$sql = "UPDATE $f_table
				SET $f_left = IF ($f_left > $node_left,
				$f_left - $node_temp, $f_left),
				$f_right = IF ($f_right > $node_left,
				$f_right - $node_temp, $f_right)
				WHERE ($f_right > $node_left)";
			$this->db_handle->Query($sql);
			return true;
		} else {
			// delete only this record
			// delete record
			$sql = "DELETE FROM $f_table
				WHERE $f_primary = $record_id";
			$this->db_handle->Query($sql);

			// clear blanks
			$sql = "UPDATE $f_table SET
				$f_left = IF ($f_left BETWEEN $node_left AND $node_right, $f_left - 1, $f_left),
				$f_right = IF ($f_right BETWEEN $node_left AND $node_right, $f_right - 1, $f_right),
				$f_level = IF ($f_left BETWEEN $node_left AND $node_right, $f_level - 1, $f_level),
				$f_left = IF ($f_left > $node_right, $f_left - 2, $f_left),
				$f_right = IF ($f_right > $node_right, $f_right - 2, $f_right)
				WHERE ($f_right > $node_left)";
			$this->db_handle->Query($sql);

			return true;
		}
	}


	/* moves the node '$src' and all its children (subtree) that it is the next sibling of '$dst'. */
	function nstMoveToNextSibling ( $src_id, $dst_id)
	{
		$src = $this->nstGetNodeWhere($src_id);
		$dst = $this->nstGetNodeWhere($dst_id);
		return $this->_moveSubtree ($src, $dst['r']+1);
	}

	/* moves the node '$src' and all its children (subtree) that it is the prev sibling of '$dst'. */
	function nstMoveToPrevSibling ($src_id, $dst_id)
	{
		$src = $this->nstGetNodeWhere($src_id);
		$dst = $this->nstGetNodeWhere($dst_id);
		return $this->_moveSubtree ($src, $dst['l']);
	}

	/**
	 * returns the first node that matches the '$whereclause'.
	 * The WHERE-caluse can optionally contain ORDER BY or LIMIT clauses too.
	 ***/
	function nstGetNodeWhere($id)
	{

		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$noderes['l'] = 0;
		$noderes['r'] = 0;
		$row = $this->db_handle->getRow("SELECT * FROM $f_table WHERE `$f_primary` = $id");

		$noderes['l'] = $row[$f_left];
		$noderes['r'] = $row[$f_right];
		$noderes['lvl'] = $row[$f_level];
		return $noderes;
	}

	/* '$src' is the node/subtree, '$to' is its destination l-value */
	function _moveSubtree ($src, $to)
	{
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$treesize = $src['r']-$src['l']+1;

		$this->_shiftRLValues($to, $treesize);

		if($src['l'] >= $to){ // src was shifted too?
			$src['l'] += $treesize;
			$src['r'] += $treesize;
		}
		/* now there's enough room next to target to move the subtree*/
		$newpos = $this->_shiftRLRange($src['l'],
			$src['r'], $to-$src['l']);
		/* correct values after source */
		$this->_shiftRLValues($src['r']+1, -$treesize);
		if($src['l'] <= $to){ // dst was shifted too?
			$newpos['l'] -= $treesize;
			$newpos['r'] -= $treesize;
		}
		return $newpos;
	}


	/* adds '$delta' to all L and R values that are >= '$first'.
		'$delta' can also be negative. */
	function _shiftRLValues ($first, $delta)
	{
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$this->db_handle->query("UPDATE $f_table SET $f_left =$f_left +$delta WHERE $f_left>=$first");
		$this->db_handle->query("UPDATE $f_table SET $f_right=$f_right+$delta WHERE $f_right>=$first");
	}

	/* adds '$delta' to all L and R values that are >= '$first' and <= '$last'. '$delta' can also be negative.
	   returns the shifted first/last values as node array.
	 */
	function _shiftRLRange ($first, $last, $delta)
	{
		$f_table = $this->db_table;
		$f_primary = $this->primary;
		$f_left = $this->left;
		$f_right = $this->right;
		$f_level = $this->level;

		$this->db_handle->query("UPDATE $f_table SET $f_left=$f_left+$delta WHERE $f_left>=$first AND $f_left<=$last");
		$this->db_handle->query("UPDATE $f_table SET $f_right=$f_right+$delta WHERE $f_right>=$first AND $f_right<=$last");
		return array(
			'l'=>$first+$delta, 'r'=>$last+$delta
		);
	}
}
?>